Dynamic Programming based Graph Algorithms

These class of algorithms takes a Graph as input, using it’s adjacancy matrix , generates result matrix. Some examples are

• Transitive clousure of graph
• All pair shortest path problem

Standard import statement

from openanalysis.matrix_animator import MatrixAnimator
import numpy as np       # Needed to work with arrays

Implementation Notes

• The algorithm should be implemented as a method
• The algorithm works on a networkx graph
• Obtain the adjacancy matrix as follws

def algorithm_name(G):
    import networkx as nx
    M = nx.to_numpy_matrix(G)
    # do other work now

• If Graph is weighted, matrix elements are weights. Default weight for an edge is 1. If an edge doesn’t exsist, its weight will be treated as 0. When working with weighted graphs, You have to MANUALLY set those weigthts to infinity.

m, n = M.shape
for i in range(0, n):
    for j in range(0, n):
        if i != j and D[i, j] == 0:
           M[i, j] = float('inf')

• After each change in matrix, yield matrix, yield copy of current version of matrix, along with a tuple containing current 3 co-ordinates at which change is caused

yield np.array(D), (i, j, k)

Example Warshall- Floyd Algorithm

Warshal-Floyd Algorithm computes All Pair Shortest Paths of a Graph using its adjacancy matrix

Now, Let’s implement the algorithm

def Floyd_Warshall(G):                # Must have signature like this
    D = nx.to_numpy_matrix(G)         # Obtaining Adj. matrix
    m, n = D.shape
    for i in range(0, n):             # Making non-diagonal zeros to infinity, as it is a Weighted Graph
        for j in range(0, n):
            if i != j and D[i, j] == 0:
                D[i, j] = float('inf')
    yield np.array(D), (0, 0, 0)      # Starting yield
    count = 0
    for k in range(0, n):
        for i in range(0, n):
            for j in range(0, n):
                if D[i, j] > D[i, k] + D[k, j]:
                    yield np.array(D), (i, j, k)  # yield as array changes
                    D[i, j] = D[i, k] + D[k, j]
                count += 1
    yield np.array(D), (0, 0, 0)

Visualizing the Algorithm - MatrixAnimator class

• __init__(self, fn, G):
  • fn : A function yielding matrix along with 3-tuple
  • G : Graph on which fn has to be applied and visualized
• animate(self, save=False):
  • save is True implies animation is saved in output/ folder
• apply_to_graph(self, show_graph=True):
  • applies self.fn to self.G and displays the result
  • show_graph is True implies Graph is shown along with adjacancy matrix and final matrix

Here we shall create a matrix from numpy array, and assign random weights to its edges. Then we apply our function to graph

import networkx as nx
M = nx.from_numpy_matrix(
    np.matrix(
        [[0, 1, 0, 0, 1, 0],
         [1, 0, 1, 0, 1, 0],
         [0, 1, 0, 1, 0, 0],
         [0, 0, 1, 0, 1, 1],
         [1, 1, 0, 1, 0, 0],
         [0, 0, 0, 1, 0, 0]]
    ))
import random
for u, v in M.edges():
    M.edge[u][v]['weight'] = random.randint(1, 10)
animator = MatrixAnimator(Floyd_Warshall, M)
animator.apply_to_graph()

After executing

animator.animate(save=True)

go to output/ directory to see the mp4 files

Example File

You can see more examples at Github